//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "allocator.h"
#include "iterator.h"
#include "algobase.h"
#include "forward.h"


FC_NAMESPACE_BEGIN


template <class T, class Ptr, class Ref>
class circular_buffer_iterator
{
public:
	//iterator_category - std required
	typedef std::random_access_iterator_tag						iterator_category;
	typedef random_access_iterator_tag							iterator_type;

	typedef T													value_type;
	typedef Ptr													pointer;
	typedef Ref													reference;
	typedef ptrdiff_t											difference_type;
	typedef circular_buffer<T>									buffer_type;
	typedef circular_buffer_iterator<T, Ptr, Ref>				this_type;

	circular_buffer_iterator() : buffer(0), ptr(0) {}
	explicit circular_buffer_iterator( const buffer_type* b, T* p ) : buffer(b), ptr(p) {}
	circular_buffer_iterator( const this_type& it ) : buffer(it.buffer), ptr(it.ptr) {}

	template <class U, class V>
	circular_buffer_iterator( const circular_buffer_iterator<T, U, V>& it ) : buffer(it.buffer), ptr((T*)it.ptr) {}

	pointer base() const { return ptr; }

	pointer	operator ->() const { FC_ASSERT(ptr); return ptr; }
	reference operator *() const { FC_ASSERT(ptr); return *ptr; }
	reference operator []( difference_type i ) const { return *(*this + i); }

	this_type& operator ++()
	{
		buffer->increment(ptr);
		if( ptr == buffer->m_tail )
			ptr = 0;
		return *this;
	}

	this_type& operator --()
	{
		if( ptr == 0 )
			ptr = buffer->m_tail;
		buffer->decrement(ptr);

		return *this;
	}

	template <class U, class V> bool operator ==( const circular_buffer_iterator<T, U, V>& b ) { return ptr == b.ptr; }
	template <class U, class V> bool operator !=( const circular_buffer_iterator<T, U, V>& b ) { return ptr != b.ptr; }

	this_type operator ++(int) { this_type temp(*this); ++*this; return temp; }
	this_type operator --(int) { this_type temp(*this); --*this; return temp; }

	ptrdiff_t operator - ( const this_type& it ) const
	{
		return ptrdiff_t(buffer->linear_offset(ptr) - buffer->linear_offset(it.ptr));
	}

	this_type  operator + ( difference_type i ) const { return this_type(*this) += i; }
	this_type  operator - ( difference_type i ) const { return this_type(*this) -= i; }
	this_type& operator +=( difference_type i )
	{
		if( i < 0 ) i += (difference_type)buffer->capacity();
		ptr = buffer->increment_offset(ptr, i);
		if( ptr == buffer->m_tail )
			ptr = 0;
		return *this;
	}

	this_type& operator -=( difference_type i )
	{
		if( i < 0 ) *this += -i;
		else ptr = buffer->decrement_offset(ptr ? ptr : buffer->m_tail, i);
		return *this;
	}

	bool operator <( const this_type& it ) const { return buffer->linear_offset(ptr) < buffer->linear_offset(it.ptr); }
	bool operator >( const this_type& it ) const { return it < *this; }
	bool operator <=( const this_type& it ) const { return !(it < *this); }
	bool operator >=( const this_type& it ) const { return !(*this < it); }

	void normalize()
	{
		if( ptr == 0 )
			ptr = buffer->m_tail;
	}

protected:
	// friend iterator class access
	template <class Q, class U, class V> friend class circular_buffer_iterator;
	template <class U, class V> friend class circular_buffer;
	template <class U, class V> friend class deque;

	const buffer_type* buffer;
	T* ptr;

};


template <class T, class Ptr, class Ref> inline
	circular_buffer_iterator<T, Ptr, Ref> operator +( ptrdiff_t i, const circular_buffer_iterator<T, Ptr, Ref>& it )
	{
		return it + i;
	}

template <class T, class Ptr, class Ref> inline
	circular_buffer_iterator<T, Ptr, Ref> operator -( ptrdiff_t i, const circular_buffer_iterator<T, Ptr, Ref>& it )
	{
		return it - i;
	}



template <class T, class Allocator>
class circular_buffer
{
public:
	typedef circular_buffer<T, Allocator>						this_type;
	typedef size_t												size_type;
	typedef T													value_type;
	typedef T*													pointer;
	typedef const T*											const_pointer;
	typedef T&													reference;
	typedef const T&											const_reference;
	typedef circular_buffer_iterator<T, T*, T&>					iterator;
	typedef circular_buffer_iterator<T, const T*, const T&>		const_iterator;
	typedef fc::reverse_iterator<iterator>						reverse_iterator;
	typedef fc::reverse_iterator<const_iterator>				const_reverse_iterator;
	typedef ptrdiff_t											difference_type;
	typedef Allocator											allocator_type;

	// friend iterator class access
	template <class Q, class U, class V> friend class circular_buffer_iterator;

	circular_buffer()
		: m_data(0), m_head(0), m_tail(0), m_capacity(0), m_size(0), m_allocator()
		{
		}

	explicit circular_buffer( const allocator_type& alloc )
		: m_data(0), m_head(0), m_tail(0), m_capacity(0), m_size(0), m_allocator(alloc)
		{
		}

	circular_buffer( size_t n, const T& value )
		: m_data(0), m_head(0), m_tail(0), m_capacity(0), m_size(0), m_allocator()
		{
			assign(n, value);
		}

	template <class InputIterator>
	circular_buffer( InputIterator first, InputIterator last )
		: m_data(0), m_head(0), m_tail(0), m_capacity(0), m_size(0), m_allocator()
		{
			assign(first, last);
		}

	circular_buffer( const this_type& b )
		: m_allocator()
		{
			assign( b.begin(), b.end() );
		}

	~circular_buffer()
		{
			clear();
			deallocate();
		}

	bool empty() const		{ return m_size == 0; }
	bool full() const		{ return m_size == size_t(m_capacity - m_data); }
	size_t size() const		{ return m_size; }
	size_t capacity() const	{ return size_t(m_capacity - m_data); }
	size_t unused() const	{ return size_t(m_capacity - m_data) - m_size; }

	reference operator [] ( size_t i ) { return *increment_offset(m_head, i); }
	const_reference operator [] ( size_t i ) const { return *increment_offset(m_head, i); }

	reference at( size_t i )
	{
		FC_ASSERT(i < size());
		return *increment_offset(m_head, i);
	}

	const_reference at( size_t i ) const
	{
		FC_ASSERT(i < size());
		return *increment_offset(m_head, i);
	}

	reference		front()			{ return *m_head; }
	const_reference front() const	{ return *m_head; }
	reference		back()			{ return *get_tail(); }
	const_reference back()	const	{ return *get_tail(); }
	iterator		begin()			{ return iterator(this, m_head); }
	const_iterator	begin() const	{ return const_iterator(this, m_head); }
	iterator		end()			{ return iterator(this, 0); }
	const_iterator	end() const		{ return const_iterator(this, 0); }
	const_iterator	cbegin() const			{ return const_iterator(this, m_head); }
	const_iterator	cend() const			{ return const_iterator(this, 0); }
	const_reverse_iterator	crbegin() const	{ return const_reverse_iterator(end()); }
	const_reverse_iterator	crend() const	{ return const_reverse_iterator(begin()); }
	reverse_iterator		rbegin()		{ return reverse_iterator(end()); }
	const_reverse_iterator	rbegin() const	{ return const_reverse_iterator(end()); }
	reverse_iterator		rend()			{ return reverse_iterator(begin()); }
	const_reverse_iterator	rend() const	{ return const_reverse_iterator(begin()); }

	pointer			linear_begin()			{ return m_head; }
	const_pointer	linear_begin() const	{ return m_head; }
	pointer			linear_end()			{ return m_tail; }
	const_pointer	linear_end() const		{ return m_tail; }

	allocator_type&			get_allocator()			{ return m_allocator; }
	const allocator_type&	get_allocator() const	{ return m_allocator; }
	void set_allocator( const allocator_type& alloc ) { m_allocator = alloc; }

	template <class InputIterator>
	void assign( InputIterator first, InputIterator last )
	{
		AssignDispatch( first, last,
			typename is_integral<InputIterator>::type() );
	}

	template <class ForwardIterator>
	void assign_iter( ForwardIterator first, ForwardIterator last )
	{
		AssignIterator( first, last, typename is_pod<T>::type() );
	}

	void assign( size_t n, const T& value )
	{
		AssignValues( n, value, typename is_pod<T>::type() );
	}

	void pop_back()
	{
		decrement(m_tail);
		fc::destroy(m_tail);
		--m_size;
	}

	void pop_front()
	{
		fc::destroy(m_head);
		increment(m_head);
		--m_size;
	}

	void clear()
	{
		fc::destroy_range( begin(), end() );
		m_head = m_tail = m_data;
		m_size = 0;
	}

	void reset()
	{
		m_head = m_tail = m_data;
		m_size = 0;
	}

	void reserve( size_t n )
	{
		if( n > capacity() )
			set_capacity(n);
	}

	void shrink_to_fit() { set_capacity(m_size); }
	void set_capacity( size_t newCapacity )
	{
		// only reallocate if capacity is being changed
		if( newCapacity != size_t(m_capacity - m_data) )
		{
			if( newCapacity < m_size )
			{
				fc::destroy_range( begin() + newCapacity, end() );
				m_tail = decrement_offset(m_tail, newCapacity - m_size);
			}

			T* newBegin = newCapacity ? reallocate( newCapacity, begin(), end() ) : 0;
			fc::destroy_range( begin(), end() );
			deallocate();

			m_data = m_head = m_tail = newBegin;
			m_capacity = newBegin + newCapacity;
		}
	}

	void push_back( const T& value = T() )
	{
		FC_ASSERT(m_capacity);
		if( full() )
		{
			*m_tail = value;
			increment(m_head);
			m_tail = m_head;
		}
		else
		{
			fc::construct(m_tail, value);
			increment(m_tail);
			++m_size;
		}
	}

	void push_front( const T& value = T() )
	{
		FC_ASSERT(m_capacity);
		decrement(m_head);
		if( full() )
		{
			*m_head = value;
			m_tail = m_head;
		}
		else
		{
			fc::construct(m_head, value);
			++m_size;
		}
	}

	void make_linear()
	{
		if( !is_linear() )
		{
			//todo: can this be done without an allocation?
			fc::reverse_copy( begin(), end(), m_data + m_size );
			m_head = m_data;
			m_tail = m_data + m_size;
		}
	}

	this_type& operator =( const this_type& b )
	{
		if( this != &b )
			assign_iter( b.begin(), b.end() );

		return *this;
	}


	void swap( this_type& x )
	{
		if( m_allocator == x.m_allocator )
		{
			fc::swap( m_data, x.m_data );
			fc::swap( m_head, x.m_head );
			fc::swap( m_tail, x.m_tail );
			fc::swap( m_capacity, x.m_capacity );
			fc::swap( m_size, x.m_size );
		}
		else
		{
			this_type temp(*this);
			*this = x;
			x = temp;
		}
	}

	T* get_head() const { return m_head; }
	T* get_tail() const { return (m_tail == m_data ? m_capacity : m_tail) - 1; }

	// internal offset range utility functions.
	//
	// Keeps pointers and indices to [0, size) within range of [head, tail), which are necessarry for
	// random access lookup within the array when the circular buffer is not linearized.
	// Raw pointer manipulation on a circular buffer is only safe when is_linear() == true,
	// in which case data is guaranteed to be contiguous.

	inline bool is_linear() const
	{
		return (m_head < m_tail || m_size == 0 || m_tail == m_data);
	}

	inline void increment( T*& p ) const
	{
		++p;
		if( p == m_capacity )
			p = m_data;
	}

	inline void decrement( T*& p ) const
	{
		if( p == m_data )
			p = m_capacity;
		--p;
	}

	inline T* increment_offset( const T* ptr, ptrdiff_t i ) const
	{
		return (T*)((ptr + i < m_capacity) ? ptr + i : ptr + i - (ptrdiff_t)capacity());
	}

	inline T* decrement_offset( const T* ptr, ptrdiff_t i ) const
	{
		return (T*)((ptr - i < m_data) ? ptr - i + (ptrdiff_t)capacity() : ptr - i);
	}

	inline T* linear_offset( const T* p ) const
	{
		if( !p )
			return m_head + m_size;
		return (T*)((p < m_head) ? p + (m_capacity - m_data) : p);
	}

	bool iterator_is_valid( const_iterator it ) const
	{
		it.normalize();
		return (it.ptr >= m_data && it.ptr <= m_capacity);
	}

protected:
	template <class InputIterator>
	inline void AssignDispatch( InputIterator first, InputIterator last, const false_type& )
	{
		AssignIterator( first, last, typename is_pod<T>::type() );
	}

	template <class Integral>
	inline void AssignDispatch( Integral n, Integral value, const true_type& )
	{
		AssignValues( (size_t)n, (T)value, typename is_pod<T>::type() );
	}

	template <class ForwardIterator>
	void AssignIterator( ForwardIterator first, ForwardIterator last, true_type )
	{
		const size_t n = fc::distance(first, last);
		if( FC_UNLIKELY(n > capacity()) )
		{
			deallocate();
			T* newBuffer = reallocate( n, first, last );
			m_data = m_head = newBuffer;
			m_tail = m_capacity = newBuffer + n;
			m_size = n;
		}
		else
		{
			T* newEnd = fc::copy( first, last, m_data );
			m_head = m_data;
			m_tail = (newEnd == m_capacity) ? m_head : newEnd;
			m_size = n;
		}
	}

	template <class ForwardIterator>
	void AssignIterator( ForwardIterator first, ForwardIterator last, false_type )
	{
		const size_t n = fc::distance(first, last);
		if( FC_UNLIKELY(n > capacity()) )
		{
			fc::destroy_range( begin(), end() );
			deallocate();

			T* newBuffer = reallocate( n, first, last );
			m_data = m_head = newBuffer;
			m_tail = m_capacity = newBuffer + n;
			m_size = n;
		}
		else
		if( n > size() )
		{
			ForwardIterator mid = first;
			fc::advance( mid, size() );

			iterator newTail = fc::copy( first, mid, begin() );
			newTail = fc::uninitialized_copy( mid, last, newTail );
			m_tail = newTail.base();
		}
		else
		{
			iterator newEnd = fc::copy( first, last, begin() );
			fc::destroy_n( newEnd, size_t(end() - newEnd) );
			m_tail = newEnd.base();
		}
	}

	void AssignValues( size_t n, const T& value, true_type )
	{
		if( FC_UNLIKELY(n > capacity()) )
		{
			deallocate();
			T* newBuffer = allocate(n);
			fc::fill_n( newBuffer, n, value );

			m_data = m_head = newBuffer;
			m_tail = m_capacity = newBuffer + n;
			m_size = n;
		}
		else
		{
			m_tail = fc::fill_n( m_data, n, value );
			m_head = m_data;
			m_size = n;
		}
	}

	void AssignValues( size_t n, const T& value, false_type )
	{
		if( FC_UNLIKELY(n > capacity()) )
		{
			fc::destroy_range( begin(), end() );
			deallocate();
			T* newBuffer = allocate(n);
			fc::uninitialized_fill_n( newBuffer, n, value );

			m_data = m_head = newBuffer;
			m_tail = m_capacity = newBuffer + n;
			m_size = n;
		}
		else
		if( n > m_size )
		{
			fc::fill( begin(), end(), value );
			fc::uninitialized_fill( end(), begin() + n, value );
			m_tail = increment_offset( m_tail, n - m_size );
		}
		else
		{
			iterator newEnd = fc::fill_n( begin(), n, value );
			fc::destroy_range( newEnd, end() );
			m_tail = decrement_offset( m_tail, m_size - (m_size - n) );
		}
	}

	T* allocate( size_t n )
	{
		return (T*)(n ? m_allocator.allocate( n * sizeof(T) ) : 0);
	}

	void deallocate()
	{
		if( m_data )
			m_allocator.deallocate( (void*)m_data, size_t(m_capacity - m_data) * sizeof(T) );
	}

	template <class ForwardIterator>
	T* reallocate( size_t newCapacity, ForwardIterator first, ForwardIterator last )
	{
		T* p = allocate(newCapacity);
		fc::uninitialized_copy( first, last, p );
		return p;
	}

	pointer m_data;
	pointer m_head;
	pointer m_tail;
	pointer m_capacity;
	size_t m_size;
	allocator_type m_allocator;

};



// global circular_buffer operators

template <class T, class Allocator> inline
	void swap( const circular_buffer<T, Allocator>& a, const circular_buffer<T, Allocator>& b )
	{
		a.swap(b);
	}

template <class T, class A1, class A2> inline
	bool operator ==( const circular_buffer<T, A1>& a, const circular_buffer<T, A2>& b )
	{
		return( &a == &b || (a.size() == b.size() && fc::equal(a.begin(), a.end(), b.begin())) );
	}

template <class T, class A1, class A2> inline
	bool operator !=( const circular_buffer<T, A1>& a, const circular_buffer<T, A2>& b )
	{
		return !(a == b);
	}

template <class T, class A1, class A2> inline
	bool operator <( const circular_buffer<T, A1>& a, const circular_buffer<T, A2>& b )
	{
		return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
	}

template <class T, class A1, class A2> inline
	bool operator >( const circular_buffer<T, A1>& a, const circular_buffer<T, A2>& b )
	{
		return b < a;
	}

template <class T, class A1, class A2> inline
	bool operator <=( const circular_buffer<T, A1>& a, const circular_buffer<T, A2>& b )
	{
		return !(b < a);
	}

template <class T, class A1, class A2> inline
	bool operator >=( const circular_buffer<T, A1>& a, const circular_buffer<T, A2>& b )
	{
		return !(a < b);
	}



FC_NAMESPACE_END
